
#include "preprocesamiento.h"
#include "huffman.h"

#define TAM_VFREC 256

//const int TAM_VFREC = 255;
    


int crearNodo(nodoArbol* *arbol, datoArbol dato){
        
	nodoArbol*nuevo = (nodoArbol*)malloc(sizeof(nodoArbol));
	if(!nuevo) return -1;
	nuevo->dato = dato;
	nuevo->h_izq = NULL;
	nuevo->h_der = NULL;
	*arbol = nuevo;
	return 0;
}


//////////////////////////////
/* Esta funcion se encarga de ordenar de mayor a menor el vector de arboles
de acuerdo a la frecuencia del caracter que contiene cada una de las hojas */
void ordenar(nodoArbol** vec_arb,int n)
{
	int i;
	nodoArbol* aux;
	bool ordenado = false;

	while(!ordenado)
	{
		ordenado=true;
		for(i=0;i<n-1;i++)
			if (vec_arb[i]->dato.frec<vec_arb[i+1]->dato.frec)
			{
				ordenado = false;
				aux = vec_arb[i];
				vec_arb[i] = vec_arb[i+1];
				vec_arb[i+1] = aux;
			};
	};
}


/* Esta funcion se encarga de crear una hoja de arbol por cada caracter con
repeticion distinta de cero colocandola en un vector de hojas. Luego se
ordena dicho vector de acuerdo a la frecuencia de aparicion de cada caracter.
Por ultimo se procede a generar el arbol de Huffman reasignando punteros
sobre dicho vector de subarboles */
nodoArbol* armar_arbol2(vFrecuencias_t* vFrecuencias, int tam_vfrec)
{/* aca pordira solo usar i porque lo generramos completo*/
	int i,j=0;
	datoArbol dato_aux;
	nodoArbol* aux;
	nodoArbol* vec_arb[tam_vfrec];

	for(i=0;i<256;i++)
	{
		if(vFrecuencias[i].frec>0)
		{
			dato_aux.ch=vFrecuencias[i].ch;
			dato_aux.frec = vFrecuencias[i].frec;
			crearNodo(vec_arb+j,dato_aux);
			j++;
		};
        };
	ordenar(vec_arb,j);

	while(j>1)
	{
		dato_aux.frec=vec_arb[j-2]->dato.frec + vec_arb[j-1]->dato.frec;
                dato_aux.ch='a';
		crearNodo(&aux,dato_aux);
		aux->h_izq = vec_arb[j-2];
		aux->h_der = vec_arb[j-1];
		i = j-2;
		while((i>0)&&(aux->dato.frec>vec_arb[i-1]->dato.frec))
		{
			vec_arb[i] = vec_arb[i-1];
			i--;
		};
		vec_arb[i] = aux;
		j--;
	};

	

	return vec_arb[0];
}
/////////////////////////////
    /*asd
     * Método semi dinámico:
     * Comprime caracteres leídos como si fuera dinámico, pero rearmando el árbol 
     * cada cierta cantidad de caracteres.
     * 
     * Algoritmo de armado del árbol:
    The simplest construction algorithm uses a priority queue where the node with lowest probability is given highest priority:

    Create a leaf node for each symbol and add it to the priority queue.
    While there is more than one node in the queue:
        Remove the two nodes of highest priority (lowest probability) from the queue
        Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
        Add the new node to the queue.
    The remaining node is the root node and the tree is complete.

     */


//            /* ALGUNAS FUNCIONES INÚTILES PARA IMPRIMIR DATOS*/
//
//void imprimir_vNodo(nodoArbol** vNodo, int tamanio){
//    cout << "IMPRIMIENDO vNodo" << endl;
//    cout << "pos-char-frec" << endl;
//    //nodoArbol nodo;
//    for (int i = 0 ; i < tamanio; i++){
//        cout << vNodo[i]->dato.ch;
//        /*if ( !*vNodo[i]->ch) {
//            cout << i << ": " << "NO TIENE" << " - " << *vNodo[i]->frec << endl;
//        }else{
//            cout << i << ": " << *vNodo[i]->ch << " - " << *vNodo[i]->frec << endl;  
//        }*/
//    }
//    cout << "FIN vNodo" << endl;
//}
//
//void imprimir_vFrec(vFrecuencias_t* vFrec, int tamanio){
//    cout << "IMPRIMIENDO vFrec" << endl;
//    cout << "pos-char-frec" << endl;
//    int res = 0;
//    for (int i = 0 ; i < tamanio; i++){
//        cout << i << ": " << vFrec[i].ch << " - " << vFrec[i].frec << endl;
//        res += vFrec[i].frec;
//    }
//    
//    cout << "FIN vFrec" << endl;
//    cout << "CANTIDAD = " << res << endl;
//}
//
//void contar_frecuencias(vFrecuencias_t* vFrec, int tamanio){
//    cout << "CONTANDO FRECUENCIAS" << endl;
//    int res = 0;
//    for (int i = tamanio ; i >= 0; i--){
//        cout << vFrec[i].frec << "-"; 
//        res += vFrec[i].frec;
//    }
//    cout << "CANTIDAD = " << res << endl;
//}
//
//            /* FIN FUNCIONES INÚTILES */


//Crea y devuelve un nuevo nodo a partir de la union de los pasados por parámetro


nodoArbol* unir_nodos(nodoArbol* nodo1, nodoArbol* nodo2){
    
    nodoArbol* nodo;
    datoArbol dato;
    dato.frec = nodo1->dato.frec + nodo2->dato.frec;
    dato.ch='a';
    
    if(crearNodo(&nodo,dato)!=0){
        cout << "Error al crear nodo" << endl;
        //return -1; 
    }
    
    nodo->h_izq = nodo1;                                         
    nodo->h_der = nodo2;
    
    return nodo;
}

//Compara 2 nodos por frecuencia primero y si son iguales por char
int cmp_nodos(nodoArbol* nodo1, nodoArbol* nodo2){
    if (nodo1->dato.frec > nodo2->dato.frec) return 1;
    if (nodo1->dato.frec < nodo2->dato.frec) return -1;
    
   // if (nodo1->dato.ch > nodo2->dato.ch) return 1;
  //  if (nodo1->dato.ch < nodo2->dato.ch) return -1;
    return 0;
    
}

void swap_nodos(nodoArbol* elem1,nodoArbol* elem2){

    nodoArbol temp = *elem1;
    *elem1 = *elem2;
    *elem2 = temp;

}

//Recibe un vector de nodos ordenado salvo por el elemento en la posicion pasada por parametro.
//Ordena el vector desplazando dicho elemento a la izquierda hasta encontrar su posicion.
void reubicar_nodo(nodoArbol** vNodos, int posicion){
    
//    file << "Reubico vNodo[" << posicion << "]" << endl; 
    
    while ( posicion >= 1 && cmp_nodos( vNodos[posicion], vNodos[posicion-1]) >= 0){
        swap_nodos( vNodos[posicion], vNodos[posicion-1]);
        //file << "Swapeo vNodo[" << posicion << "]" << " y vNodo[" << posicion-1 << "]" << endl;
        posicion--;
    }
}

//Original de lista enlazada
void reordenar_lista(listaEnlazada* lista){
    nodoLE* nodo = lista->ult;
    if (nodo->ant == NULL) return; //ya está ordenado
    nodoLE* nodoAcomp = nodo->ant;
    nodoLE* nodoAnterior = nodo;
    
    while (nodoAcomp != NULL && cmp_nodos(nodo->dato, nodoAcomp->dato) > 0){
        nodoAnterior = nodoAcomp;
        nodoAcomp = nodoAcomp->ant;
    }
    
    if(nodoAnterior == nodo) return; //caso borde, lista ordenada por defecto
    lista->ult = nodo->ant;
    nodo->ant = nodoAcomp;
    nodoAnterior->ant = nodo;
    if (nodoAcomp == NULL)  lista->pri = nodo;
    
}

//Optimización de lista enlazada
void reordenar_lista2(listaEnlazada* lista){
    nodoLE* nodo = lista->pri;
    if (nodo == lista->ult) return; //ya está ordenado
    nodoLE* nodoAcomp = nodo->sig;

    while (nodoAcomp != NULL && cmp_nodos(nodo->dato, nodoAcomp->dato) < 0){
        nodoAcomp = nodoAcomp->sig;
    }
    
    if (nodoAcomp == NULL){
        //cout << "987" << endl;
        lista->pri = nodo->sig;
        lista->pri->ant = NULL;
        lista->ult->sig = nodo;
        nodo->ant = lista->ult;
        lista->ult = nodo;
       // cout << "888" << endl;
        
    }else if (nodo->sig == nodoAcomp){
        return;
    }else{
       // cout << "11" << endl;
        lista->pri = nodo->sig;
        lista->pri->ant = NULL;
        nodoAcomp->ant->sig = nodo;
        //cout << "12" << endl;
        nodo->ant = nodoAcomp->ant;
        nodo->sig = nodoAcomp;
        nodoAcomp->ant = nodo;
       // cout << "13" << endl;
    }
          
    //if (nodoAcomp->ant == nodo) return; //ya está ordenado


    
   // //if(nodoSig == nodo) return; //caso borde, lista ordenada por defecto
   // lista->pri = nodo->sig;
   // nodo->ant = nodoAcomp;

    //if (nodoAcomp == NULL)  lista->pri = nodo;
    
}

//Inicia el vector de frecuencias con todos los caracteres en 1
void iniciar_vFrecuencias(vFrecuencias_t* vectorF,const int tam){

    //Inicializo el vector de frecuencias en 1
    for(int i = 0; i < tam; i++){
        vectorF[i].ch = (unsigned char)i;
        vectorF[i].frec = 1;
    }
}


nodoLE* crearNodoLE( nodoArbol* dato){
        
	nodoLE* nuevo = (nodoLE*)malloc(sizeof(nodoLE));
	if(!nuevo) return NULL;
	nuevo->dato = dato;
	nuevo->ant = NULL;
	nuevo->sig = NULL;
	return nuevo;
}

listaEnlazada* crearLE(){
    listaEnlazada* nuevo = (listaEnlazada*)malloc(sizeof(listaEnlazada));
    if(!nuevo) return NULL;
    nuevo->pri = NULL;
    nuevo->ult = NULL;
    return nuevo;
}



//funcion original de lista enlazada
void unir_nodos2(listaEnlazada* lista){
    nodoLE* nodo1 = lista->ult;
    if (nodo1 == NULL) cout << "ERROR EN UNIR_NODOS2 (1)" << endl;
    nodoLE* nodo2 = nodo1->ant;
    if (nodo2 == NULL)  cout << "ERROR EN UNIR_NODOS2 (2)" << endl;
    nodoArbol* nodoA = unir_nodos(nodo1->dato, nodo2->dato);
    nodoLE* nuevoNodo = crearNodoLE(nodoA);
    if (nuevoNodo == NULL) cout << "ERROR EN UNIR_NODOS2 (3)" << endl;
    nuevoNodo->ant = nodo2->ant;
    lista->ult = nuevoNodo;
    if (nuevoNodo->ant == NULL) lista->pri = nuevoNodo;
    free(nodo1);
    free(nodo2);
}


//funcion de lista enlazada optimizada
void unir_nodos3(listaEnlazada* lista){
    nodoLE* nodo1 = lista->ult;
    if (nodo1 == NULL) cout << "ERROR EN UNIR_NODOS2 (1)" << endl;
    nodoLE* nodo2 = nodo1->ant;
    if (nodo2 == NULL)  cout << "ERROR EN UNIR_NODOS2 (2)" << endl;
    nodoArbol* nodoA = unir_nodos(nodo1->dato, nodo2->dato);
    nodoLE* nuevoNodo = crearNodoLE(nodoA);
    if (nuevoNodo == NULL) cout << "ERROR EN UNIR_NODOS2 (3)" << endl;
    
    if (nodo2 == lista->pri) {
        lista->pri = nuevoNodo;
        lista->ult = nuevoNodo;
        //cout << "123" << endl;
    }else{
        nuevoNodo->sig = lista->pri;
        lista->pri->ant = nuevoNodo;
        lista->pri = nuevoNodo;
        lista->ult = nodo2->ant;
       // cout << "456" << endl;
        lista->ult->sig = NULL;
        //cout << "678" << endl;
    }
    
    free(nodo1);
    //cout << "asd" << endl;
    free(nodo2);
   // cout << "gfds" << endl;
}

//Imprime la lista enlazada
void imprimir_lista(listaEnlazada* lista){
    nodoLE* nodo = lista->pri;
    int i = 0;
    while (nodo != lista->ult){
        if (nodo->dato->dato.frec > 1){
            cout << "_N_" << "-" << nodo->dato->dato.frec << endl;
        }else
        cout << i << "-->" << nodo->dato->dato.ch << "-" << nodo->dato->dato.frec << endl;
        nodo = nodo->sig;
        i++;
    }
    cout << nodo->dato->dato.ch << "-" << nodo->dato->dato.frec << endl;
    //cout << "char ant: " << nodo->ant->ant->dato->dato.ch << endl;

}

//Crea un árbol de huffman a partir del vector de frecuencias y su tamaño pasados por parámetro.
//Devuelve un puntero al nodo raíz del árbol
nodoArbol* armar_arbol(vFrecuencias_t* vFrecuencias, int tam_vfrec){
    
    //nodoArbol* vNodos[tam_vfrec];
   // int j = tam_vfrec -1;
    
    //file << endl << "Imprimo las hojas de arbol a crear: " << endl;
    
    // Crea una hoja (nodoArbol) para cada caracter y almacena un puntero en el
    // array vNodos con chars de menor frecuencia al final.
    
    listaEnlazada* lista = crearLE();
    if (lista == NULL){
        cout << "ERROR CREANDO LISTA ENLAZADA" << endl;
        return NULL;
    }
    
    for(int i = 0 ; i < tam_vfrec ; i++){
        
        nodoLE* nodoLista;
        nodoArbol* nodo;
        datoArbol dato;
        dato.frec = vFrecuencias[i].frec;
        dato.ch = vFrecuencias[i].ch;
        
        if(crearNodo(&nodo,dato)!=0){
            cout << "Error al crear nodo" << endl;
            //return -1; 
        } 
        nodoLista = crearNodoLE(nodo);
        if (lista->pri == NULL || lista->ult == NULL){
            lista->pri = lista->ult = nodoLista;
        }else{
            lista->pri->ant = nodoLista;
            nodoLista->sig = lista->pri;
            lista->pri = nodoLista;
        }
             
        
        //vNodos[j] = nodo;
        
        //file << "vNodo[" << j << "]: "<< vNodos[j]->dato.frec << "/" << (unsigned short)vNodos[j]->dato.ch << endl;
        
        //j--;
    }
//imprimir_vNodo(vNodos, TAM_VFREC);
    
    // Crea las uniones de los nodos para completar el árbol a partir de las hojas
    // En vez de una cola de prioridad, usamos un vector ordenado de mayor a menor y vamos agarrando los items del final
    // Agarrar los 2 últimos nodos del vNodo y crear un nodo padre con la suma de las frecuencias.
    // Sacar del vector los 2 nodos y ubicar al final el nodo padre. Reordenar el vector y repetir hasta quedar sin nodos.
    // Asignar la raiz al que corresponda.
    
    //Ojo que si el for va mientras k >= 0 se va a menos uno
    
//    file << endl << "Armando un arbol: " << endl;
    
    

   // int asd = 0;
    while (lista->ult != lista->pri){
        //cout << asd <<endl;
        unir_nodos3( lista);
        reordenar_lista2(lista);
        //if (asd == 126) {
          //  imprimir_lista(lista);
            //exit(1);
        //}
        //asd++;
        //imprimir_vNodo(vNodos, TAM_VFREC);
    }
    
    /* Procedimiento original
    for( int i = tam_vfrec -1 ; i > 0 ; i--){
        nodoArbol* nodo = unir_nodos( vNodos[i-1], vNodos[i]);
        //file << "Uni nodos " << i-1 << " y " << i <<endl;
        vNodos[i-1] = nodo;
        reubicar_nodo(vNodos, i-1);
        //imprimir_vNodo(vNodos, TAM_VFREC);
    }
     return vNodos[0];
     */
    //imprimir_vNodo(vNodos, TAM_VFREC);
    
    nodoArbol* raiz = lista->pri->dato;
    free(lista->pri);
    free(lista);
    return raiz;
}

////Crea el vector de frecuencias inicial para el árbol
//void iniciar_vFrecuencias_arbol(vFrecuencias_t* vFrecuencias, int tamanio){
//    iniciar_vFrecuencias(vFrecuencias,tamanio);
//    qsort(vFrecuencias, tamanio, sizeof(vFrecuencias_t), stringComp2);
//    //return vFrecuencias;
//}


//Dada la raiz de un arbol, borra todos sus nodos
void destruir_arbol(nodoArbol* raiz)
{
  if(raiz)
  {
    destruir_arbol(raiz->h_izq);
    destruir_arbol(raiz->h_der);
    free(raiz);    
  };

}

bool codificar_caracter(nodoArbol* raiz, stack<bool>* pila, unsigned char charR){
    
    //boolean buscar_cod(t_arbol* raiz, t_pila* pila, byte b,long *vector_frec)
    //cout << raiz->h_izq << endl;  
    if (raiz)
    {
        if ( (!raiz->h_izq) && (!raiz->h_der) && (raiz->dato.ch == charR) ){
            return true;
        }
        if (codificar_caracter(raiz->h_izq,pila,charR)){ 
            pila->push(false); return true;
        }
        if (codificar_caracter(raiz->h_der,pila,charR)){
            pila->push(true); return true;
        }
    }
    return false;
}


//sumar uno a la frecuencia del charR en el vector
int actualizarFrecuencias(vFrecuencias_t * vFrecuencias,unsigned char charR){
        
    for(int i = 0; i < TAM_VFREC; i++){
        
        if(vFrecuencias[i].ch == charR){
            
            vFrecuencias[i].frec += 1;
            
            //qsort(vFrecuencias, TAM_VFREC, sizeof(vFrecuencias_t), stringComp2);
            
            return 0;
        }        
    }        
    return -1;
}

int ordenarVFrecuencias(vFrecuencias_t* vFrecuencias){
    qsort(vFrecuencias, TAM_VFREC, sizeof(vFrecuencias_t), stringComp2);
}